1. Technical Field of the Invention
The invention pertains to a method for use in connection with an architecture synthesis engine which is disposed to generate and explore alternative system architectures for executing the functional specification of a system in the form of a task graph. More particularly, the invention pertains to a method of the above type of selectively processing or preparing a task graph to serve as a suitable input to the architecture synthesis engine. Even more particularly, the invention pertains to a method of the above type which substantially models and processes asynchronous behavior in the input functional specification.
2. Description of Related Art
As is well known in the art, a computer system typically has a large number and diversity of hardware and software resources which may be employed to execute or complete a particular functional specification. An example of a functional specification known as a task graph would be the set of tasks which must be carried out in order to operate a cellular phone for wireless communication. Generally, many different combinations of hardware and software resources are available to execute a particular task specification, including combinations of only hardware resources, of only software resources, and mixtures of both types of resources. However, while the number of workable combinations may be quite large, some resource combinations are more useful than others, and some resource combinations may have undesirable characteristics or unintended consequences. The comparative merits of different resource combinations are generally determined by timing or other constraints imposed upon implementation of a set of tasks.
As is further known in the art, architecture space exploration is the process of mapping a task specification to a set of resources and time schedules, wherein the set of tasks in the specification may be represented as a graph of interrelated processes and communications, hereinafter referred to as a task graph. The set of resources comprises objects such as software, memory elements, special application specific integrated circuits (ASICs) and processors. Each solution provided by the mapping process has a corresponding architecture, that incorporates a particular combination of resource components and assigns respective tasks to the resource components, and also schedules the timing of task completion. In the past, efforts were made to automate the process of selecting a suitable distribution of resources to define an architecture within the universe of possible architecture solutions known as the design space. Architecture synthesis algorithms were developed for the process. Some of these efforts are described, for example, in “Research Strategies for Architecture Synthesis and Partitioning of Real-Time Systems,” Jakob Axelsson, IDA Technical Report, 1996. A computing system configured in accordance with an architecture synthesis algorithm to receive a task graph and a set of resource components as inputs, and which implements the algorithm to generate and explore alternative architectures, may be referred to as an architecture synthesis engine.
The modeling of algorithms for architectural design space exploration, as described above, must consider asynchronous behavior during execution of the algorithm. Algorithms are usually synchronous and deterministic in that for a given set of data, an algorithm follows exactly the same events in the same order (i.e., the execution is predictable and repeatable). Asynchronous behavior in a system occurs when the behavior of the system is unpredictable or unrepeatable. An example of asynchronous behavior is demonstrated by a radio network controller (RNC) in a wireless communication system. The RNC is responsible for the control of radio resources by constantly monitoring bandwidth demand and availability, signal propagation efficiency, and ultimately for the load and congestion of its dominion of cells. The network environment resulting from user location, activity, and signal propagation conditions at any given time is random, hence unpredictable, and user-driven, hence unrepeatable. RNCs employ statistical methods to asynchronously regulate bandwidth allocations, signal power and regulate cell size or macro diversity.
Current architecture synthesis algorithms do not consider execution of asynchronous behavior. A non-deterministic execution of asynchronous behavior makes it difficult to model using a synchronous data flow graph (SDFG). In SDFG predictable and deterministic signals are required to compute the order of execution of every task in order to make sure the graph is viable, that is, that the graph can execute without deadlock or infinite buffer. Accordingly, what is needed is a technique for identifying asynchronous dependencies, and using such information to derive a task graph which is suitable for deterministic scheduling.